package cn.edu.leetcode.二叉树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 二叉树的所有路径 {

    public static void main(String[] args) {

        binaryTreePaths(null);
    }

    static Stack<Integer> stack = new Stack<>();


    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();

        if (root != null){
            dfs(root, list);
        }

        return list;
    }

    public static void dfs(TreeNode root, List<String> list){
        stack.push(root.val);

        if (root.left != null){
            dfs(root.left, list);
        }

        if (root.right != null){
            dfs(root.right, list);
        }

        if (root.left == null && root.right == null){

            StringBuilder builder = new StringBuilder();
            for (int x : stack) {
                builder.append(x);
                builder.append("->");
            }
            builder.deleteCharAt(builder.length()-1);
            builder.deleteCharAt(builder.length()-1);
            list.add(builder.toString());
        }

        stack.pop();
    }


}
